The present invention relates to computer generated graphics. In particular, the present invention relates to the modeling and morphing of graphics on a computer.
Computer graphics are used in many different applications including computer games, movies and web pages. With the capability of more powerful computers, realistic graphics are becoming more desired in order to provide a more realistic experience to the computer user.
One particular area of focus has been in the area of shape morphing. Shape morphing is the gradual transformation of one shape into another which has wide applications such as modeling, animation, medicine, and entertainment.
The morphing problem has been investigated in many contexts. In particular, in object-space morphing there are two subproblems which have been identified. The first problem is referred to as the vertex correspondence problem. That is determining vertex correspondence pairs in the premorphed and postmorphed shapes. The second problem is the vertex path problem. That is finding paths that the correspondence vertices traverse during the morphing process.
The establishment of suitable correspondence between shapes is a concern during shape morphing. There have been many attempts to find methods for automatically finding vertex correspondence between shapes in the prior art. For Example, Chen et al., “Shape Averaging and Its Applications to Industrial Design”, IEEE Computer Graphics and Applications, pages 47-54, 1989, attempted to automate the process of establishing correspondence by locating vertices pairs with minimum distances. Sederberg et al., “A Physically Based Approach to 2d Shape Blending”, In Proceedings SIGGRAPH '92, pages 25-34, 1992, proposed to use a physically based approach to minimize some work function to determine the correspondence between vertices. Zhang, “A Fuzzy Approach to Digital Image Warping”, IEEE Computer Graphics and Applications, pages 33-41, 1996, introduced a fuzzy vertex correspondence based on maximizing a similarity function between vertices. This method is similar to the physically based approach but uses a similarity function instead of a work function. In Ranjan et al., “Matching and Interpolation of Shapes Using Unions of Circles,” Computer Graphics Forum, Proceedings Eurographics '96, C129-C142, 1996, an object is represented by a union of circles. Correspondence is established by considering the sizes and relative locations of the circles, and in-between objects are generated by blending corresponding circles. Recently, Mortara et al., “Similarity Measures for Blending Polygonal Shapes”, Computer & Graphics, pages 13-27, 2001, used an approximate skeleton to describe the shape and established the vertex correspondence through finding a reasonable match among the approximate skeletons of the shapes.
In addition when morphing a curved shape, existing methods assume a uniformly distributed set of vertices approximating the shape. For example, Sederberg et al., “Shape Blending of 2-D Piecewise Curves”, Mathematical Methods in CAGD III, pages 1-3, 1995, extended the physically based approach set out in Sederberg et al., “A Physically Based Approach to 2d Shape Blending”, In Proceedings SIGGRAPH '92, pages 25-34, 1992, for establishing correspondence between knots of closed B-spline curves. Cohen et al., “Matching of Freeform Curves”, Computer Aided Design, pages 369-378, 1997, used an approximated solution exploiting dynamic programming over discrete sample sets of the two curves and their unit tangent vector fields. In the industrial design context, Hui et al., “A Feature-based Shape Blending Technique for Industrial Design”, Computer Aided Design, pages 823-834, 1998, advocated a technique for locating significant vertices along curved shapes, which represent shape features. Correspondences between features of the objects are then established.
The problem of vertex correspondence also arises in surface reconstruction. This problem is set out in more detail in Meyers et al., “Surface From Contours: The Correspondence and Branching Problems”, ACM Transactions on Graphics, pages 228-258, 1992, and Bajaj et al., “Arbitrary Topology Shape Reconstruction from Planar Cross Sections”, Graphics Models and Image Processing, pages 524-543, 1996, Ballard et al., “Shape Recognition and Retrieval,” Computer Vision, Prentice-Hall, New Jersey, 1992 and Sebaastian, et al. “On Aligning Curves”, IEEE Trans. On Pattern Recognition and Machine Intelligence 25, 1, pages 116-125, 2003.
Other object-space methods are designed to solve the path problem assuming that the vertex correspondence is given. The simplest interpolation technique is linear interpolation. Unfortunately, this approach can lead to undesirable results in that the intermediate shapes can shrink or contain self-intersections even though the source and target shapes are simple shapes.
Most of the solutions to the path problem concentrate on trying to eliminate shrinks and self-intersections, and preserve the geometric properties of the intermediate shapes. Recent advances such as Floater et al., “How to Morph Tiling Injectively”, Journal of Computational and Applicated Mathematics 101, 1-2, pages 117-129, 1999; Alexa et al., “As-rigid-as-possible Shape Interpolation,” In Proceedings SIGGRAPH '00, pages 157-164, 2000; Gotsman et al., “Guranteed Intersection-Free Polygon Morphing”, Computers & Graphics 25, 1, pages 67-75, 2001; Surazhsky et al., “Controllable Morphing of Compatible Planar Triangulations”, ACM TOG 20, 4, page 203-231, 2001; and Johan et al., “Blending Multiple Polygonal Shapes”, In Proc. 11th IEEE Pacific Graphics, pages 434-440, 2003, have blended two polygonal shapes by interpolating their compatible triangulations.
It can be seen that in the prior art discussed above, vertex correspondence is established by measuring the similarity between series of vertices approximating the shapes. It can be seen that correspondence between visual features other than vertices is essential to retain certain characteristics of the original shapes for morphing at a human level of competence. For instance, consider the example of morphing a dancer shape from a first shape (shown on the left of FIG. 1) into another shape (as illustrated on the right in FIG. 1). It is desirable that the visual parts such as head-1; arms-2,3; and legs-4,5 in both shapes are in correspondence. The perceptually visual parts lying in dotted regions with same reference numbers in both shapes are thus in correspondence for the two dancer shapes. The corresponding parts are to be morphed respectively from the first shape through one or more intermediate shapes to the final shape.
A distinct shape is generally interpreted as composed of some different perceptual or meaningful visual parts. Feature points are typically points on a shape that segment the shape into meaningful subparts, and play a dominant role in shape perception by humans. If the feature points are identified and matched properly for two shapes, the morphing result will conform to expected human perception.
A work by Hui et al. “A Feature-Based Shape Blending Technique for Industrial Design”, Computer Aided Design 30, 10, pages 823-834, 1998, presented a feature-based technique for establishing the correspondence between the shapes composed of curve segments in industrial design. However, the features used in their method cannot be effectively computed. Moreover, their method is not intrinsically invariant to scale and rotation, and the correspondence found by their method is not always optimal.